package io.adrainty.algorithm.leetcode.lcr;

import java.util.HashMap;
import java.util.Map;

/**
 * LCR 011. 连续数组
 * @link <a href="https://leetcode.cn/problems/A1NYOS/description/">...</a>
 * @author AdRainty
 * @version V1.0.0
 * @since 2024/9/8 下午10:06
 */
public class LCR011 {

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, -1);
        int sum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i] == 0 ? -1 : 1;
            if (preSum.containsKey(sum)) {
                // 前面有相同的前缀和，则计算当前位置和前缀和位置之间的长度，并更新最大长度
                res = Math.max(res, i - preSum.get(sum));
            } else {
                preSum.put(sum, i);
            }
        }
        return res;
    }

}
